// -*- coding: utf-8 -*-
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-14 14:30
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.DynamicPlan;

import org.junit.jupiter.api.Test;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Partition {

    public List<List<String>> partitionT(String s) {
        // 返回构建所有回文字符串
        int len = s.length();
        List<List<String>> ans = new ArrayList<>();
        Deque<String> stack = new ArrayDeque<>();
        dfsT(s, 0, len, stack, ans);
        return ans;
    }

    private void dfsT(String s, int index, int end, Deque<String> path, List<List<String>> ans) {
        if (index == end) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int i = index; i < end; i++) {
            if (!isPalindromeT(s, index, i)) {
                continue;
            }
            path.addLast(new String(s.substring(index, i + 1)));
            dfsT(s, i + 1, end, path, ans);
            path.removeLast();
        }
    }

    /**
     * 判断字符串是否是回文字符串
     */
    private boolean isPalindromeT(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }


    /**
     * 使用动态规划 + 深度优先遍历 -> 时间复杂度O(2^N)
     *
     * @param s 给定字符串
     * @return
     */
    public List<List<String>> partition(String s) {
        int n = s.length();
        // 状态数组 -> 用于保存 i - j 之间的字符串是否是回文字符串
        boolean[][] dp = new boolean[n][n];
        // 回文字符串判断
        for (int right = 0; right < n; right++) {
            for (int left = 0; left <= right; left++) {
                dp[left][right] = s.charAt(left) == s.charAt(right) && ((right - left < 3) || dp[left + 1][right - 1]);
            }
        }
        List<List<String>> ans = new ArrayList<>();
        Deque<String> stack = new ArrayDeque<>();
        dfs(s, 0, n, dp, stack, ans);
        return ans;

    }

    private void dfs(String s, int index, int end, boolean[][] dp, Deque<String> stack, List<List<String>> ans) {
        if (index == end) {
            ans.add(new ArrayList<>(stack));
            return;
        }
        for (int i = index; i < end; i++) {
            if (dp[index][i]) {
                stack.addLast(s.substring(index,i+1));
                dfs(s, i + 1,end, dp, stack, ans);
                stack.removeLast();
            }
        }
    }


    @Test
    public void shout() {
        String test = "aab";
        // System.out.println(partition(test));
    }
}
